package 笔试;
//https://leetcode-cn.com/problems/trapping-rain-water-ii/

/**
 * 给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图每个单元的高度，请计算图中形状最多能接多少体积的雨水。
 * 输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
 * 输出: 4
 * 解释: 下雨后，雨水将会被上图蓝色的方块中。总的接雨水量为1+2+1=4。
 *
 * 输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
 * 输出: 10
 *
 */
public class 接雨水 {
    public static void main(String[] args) {
        System.out.println(trapRainWater(new int[][]{{5, 5, 5, 1}, {5, 1, 1, 5}, {5, 1, 5, 5}, {5, 2, 5, 8}}));
    }
    public static   int trapRainWater(int[][] heightMap) {
        int m=heightMap.length;
        int n=heightMap[0].length;
        if(m<3||n<3){
            return 0;
        }
        int[][] min = new int[m][n];
        int k = 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0||j==0||i == m-1||j == n-1){
                    min[i][j] = heightMap[i][j];
                }else{
                    min[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        dp(heightMap,min,1,1);
        for(int i=1;i<m-1;i++){
            for(int j=1;j<n-1;j++){
                k+=(min[i][j]-heightMap[i][j]);
            }
        }
        return k;
    }
    private static void dp(int[][] heightMap,int[][] min,  int i, int j ) {
        if(i == 0 || j == 0 || i == heightMap.length - 1 || j == heightMap[0].length - 1){
            return;
        }
        int s=Math.max(heightMap[i][j],
                Math.min(Math.min(min[i-1][j],min[i][j-1]),
                        Math.min(min[i+1][j],min[i][j+1])));
        if(s != min[i][j]){
            min[i][j]= s;
            if(min[i-1][j]>s) dp(heightMap,min,i-1,j);
            if(min[i][j-1]>s) dp(heightMap,min,i,j-1);
            if(min[i+1][j]>s) dp(heightMap,min,i+1,j);
            if(min[i][j+1]>s) dp(heightMap,min,i,j+1);
        }

    }

}
